# ๊ฑฐํ ์ ๋ ฌ(Bubble Sort)
# Goal
- Bubble Sort์ ๋ํด ์ค๋ช ํ ์ ์๋ค.
- Bubble Sort ๊ณผ์ ์ ๋ํด ์ค๋ช ํ ์ ์๋ค.
- Bubble Sort์ ๊ตฌํํ ์ ์๋ค.
- Bubble Sort์ ์๊ฐ๋ณต์ก๋์ ๊ณต๊ฐ๋ณต์ก๋๋ฅผ ๊ณ์ฐํ ์ ์๋ค.
# Abstract
Bubble Sort๋ Selection Sort์ ์ ์ฌํ ์๊ณ ๋ฆฌ์ฆ์ผ๋ก ์๋ก ์ธ์ ํ ๋ ์์์ ๋์๋ฅผ ๋น๊ตํ๊ณ , ์กฐ๊ฑด์ ๋ง์ง ์๋ค๋ฉด ์๋ฆฌ๋ฅผ ๊ตํํ๋ฉฐ ์ ๋ ฌํ๋ ์๊ณ ๋ฆฌ์ฆ
์ด๋ค.
์ด๋ฆ์ ์ ๋๋ก๋ ์ ๋ ฌ ๊ณผ์ ์์ ์์์ ์ด๋์ด ๊ฑฐํ์ด ์๋ฉด์ผ๋ก ์ฌ๋ผ์ค๋ ๋ฏํ ๋ชจ์ต์ ๋ณด์ด๊ธฐ ๋๋ฌธ์ ์ง์ด์ก๋ค๊ณ ํ๋ค.
# Process (Ascending)
- 1ํ์ ์ ์ฒซ ๋ฒ์งธ ์์์ ๋ ๋ฒ์งธ ์์๋ฅผ, ๋ ๋ฒ์งธ ์์์ ์ธ ๋ฒ์งธ ์์๋ฅผ, ์ธ ๋ฒ์งธ ์์์ ๋ค ๋ฒ์งธ ์์๋ฅผ, โฆ ์ด๋ฐ ์์ผ๋ก (๋ง์ง๋ง-1)๋ฒ์งธ ์์์ ๋ง์ง๋ง ์์๋ฅผ ๋น๊ตํ์ฌ ์กฐ๊ฑด์ ๋ง์ง ์๋๋ค๋ฉด ์๋ก ๊ตํํ๋ค.
- 1ํ์ ์ ์ํํ๊ณ ๋๋ฉด ๊ฐ์ฅ ํฐ ์์๊ฐ ๋งจ ๋ค๋ก ์ด๋ํ๋ฏ๋ก 2ํ์ ์์๋ ๋งจ ๋์ ์๋ ์์๋ ์ ๋ ฌ์์ ์ ์ธ๋๊ณ , 2ํ์ ์ ์ํํ๊ณ ๋๋ฉด ๋์์ ๋ ๋ฒ์งธ ์์๊น์ง๋ ์ ๋ ฌ์์ ์ ์ธ๋๋ค. ์ด๋ ๊ฒ ์ ๋ ฌ์ 1ํ์ ์ํํ ๋๋ง๋ค ์ ๋ ฌ์์ ์ ์ธ๋๋ ๋ฐ์ดํฐ๊ฐ ํ๋์ฉ ๋์ด๋๋ค.
# Java Code (Ascending)
void bubbleSort(int[] arr) {
int temp = 0;
for(int i = 0; i < arr.length; i++) { // 1.
for(int j= 1 ; j < arr.length-i; j++) { // 2.
if(arr[j-1] > arr[j]) { // 3.
// swap(arr[j-1], arr[j])
temp = arr[j-1];
arr[j-1] = arr[j];
arr[j] = temp;
}
}
}
System.out.println(Arrays.toString(arr));
}
์ ์ธ๋ ์์์ ๊ฐฏ์๋ฅผ ์๋ฏธํ๋ค. 1ํ์ ์ด ๋๋ ํ, ๋ฐฐ์ด์ ๋ง์ง๋ง ์์น์๋ ๊ฐ์ฅ ํฐ ์์๊ฐ ์์นํ๊ธฐ ๋๋ฌธ์ ํ๋์ฉ ์ฆ๊ฐ์์ผ์ค๋ค.
์์๋ฅผ ๋น๊ตํ index๋ฅผ ๋ฝ์ ๋ฐ๋ณต๋ฌธ์ด๋ค. j๋ ํ์ฌ ์์๋ฅผ ๊ฐ๋ฆฌํค๊ณ , j-1์ ์ด์ ์์๋ฅผ ๊ฐ๋ฆฌํค๊ฒ ๋๋ฏ๋ก, j๋ 1๋ถํฐ ์์ํ๊ฒ ๋๋ค.
ํ์ฌ ๊ฐ๋ฅดํค๊ณ ์๋ ๋ ์์์ ๋์๋ฅผ ๋น๊ตํ๋ค. ํด๋น ์ฝ๋๋ ์ค๋ฆ์ฐจ์ ์ ๋ ฌ์ด๋ฏ๋ก ํ์ฌ ์์๋ณด๋ค ์ด์ ์์๊ฐ ๋ ํฌ๋ค๋ฉด ์ด์ ์์๊ฐ ๋ค๋ก ๊ฐ์ผํ๋ฏ๋ก ์๋ก ์๋ฆฌ๋ฅผ ๊ตํํด์ค๋ค.
# GIF๋ก ์ดํดํ๋ Bubble Sort
# ์๊ฐ๋ณต์ก๋
์๊ฐ๋ณต์ก๋๋ฅผ ๊ณ์ฐํ๋ฉด, (n-1) + (n-2) + (n-3) + .... + 2 + 1 => n(n-1)/2
์ด๋ฏ๋ก, O(n^2) ์ด๋ค. ๋ํ, Bubble Sort๋ ์ ๋ ฌ์ด ๋ผ์๋ ์๋ผ์๋, 2๊ฐ์ ์์๋ฅผ ๋น๊ตํ๊ธฐ ๋๋ฌธ์ ์ต์ , ํ๊ท , ์ต์
์ ๊ฒฝ์ฐ ๋ชจ๋ ์๊ฐ๋ณต์ก๋๊ฐ O(n^2) ์ผ๋ก ๋์ผํ๋ค. (๊ฐ์ ๋ Bubble Sort๊ฐ ์กด์ฌํ๊ธด ํ๋, ๊ธฐ์ด๋ฅผ ๋ค์ง๊ธฐ ์ํ ํ์ต์ด๋ฏ๋ก ๋์ด๊ฐ๊ฒ ์)
# ๊ณต๊ฐ๋ณต์ก๋
์ฃผ์ด์ง ๋ฐฐ์ด ์์์ ๊ตํ(swap)์ ํตํด, ์ ๋ ฌ์ด ์ํ๋๋ฏ๋ก O(n) ์ด๋ค.
# ์ฅ์
๊ตฌํ์ด ๋งค์ฐ ๊ฐ๋จํ๊ณ , ์์ค์ฝ๋๊ฐ ์ง๊ด์ ์ด๋ค.
์ ๋ ฌํ๊ณ ์ ํ๋ ๋ฐฐ์ด ์์์ ๊ตํํ๋ ๋ฐฉ์์ด๋ฏ๋ก, ๋ค๋ฅธ ๋ฉ๋ชจ๋ฆฌ ๊ณต๊ฐ์ ํ์๋ก ํ์ง ์๋ค. => ์ ์๋ฆฌ ์ ๋ ฌ(in-place sorting)
์์ ์ ๋ ฌ(Stable Sort) ์ด๋ค.
# ๋จ์
์๊ฐ๋ณต์ก๋๊ฐ ์ต์ , ์ต์ , ํ๊ท ๋ชจ๋ O(n^2)์ผ๋ก, ๊ต์ฅํ ๋นํจ์จ์ ์ด๋ค.
์ ๋ ฌ ๋ผ์์ง ์์ ์์๊ฐ ์ ๋ ฌ ๋์๋์ ์๋ฆฌ๋ก ๊ฐ๊ธฐ ์ํด์, ๊ตํ ์ฐ์ฐ(swap)์ด ๋ง์ด ์ผ์ด๋๊ฒ ๋๋ค.
# Conclusion
์ ๋ ฌ ์๊ณ ๋ฆฌ์ฆ ์ค์ ๊ฐ์ฅ ์ง๊ด์ ์ธ Bubble Sort์ ๋ํด ์์๋ดค๋ค. ๊ธฐ์ ๋ฉด์ ์์๋ ์ข ์ข ๋์ค๋ ์ ๋ ฌ ์๊ณ ๋ฆฌ์ฆ์ผ๋ก ์์๋๋ฉด ์ข๋ค.